package temp;

/**
 * Created by yzy on 2020-04-15 11:26
 */
public class BottomKQuestion {

    public static void main(String[] args) {

    }

    public static int bottomK(int[] arr, int k){
        int[] maxTopHeap = createMaxTopHeap(arr, k);
        for(int i=k; i<arr.length; i++){
            if(arr[i] < maxTopHeap[0]){
                putMaxTopHeap(maxTopHeap, arr[i]);
            }
        }
        return maxTopHeap[0];
    }


    public static int[] createMaxTopHeap(int[] arr, int k){
        int[] heap = new int[k];
        for(int i=0; i<k; i++){
            int childIdx = i;
            int parentIdx = (childIdx-1)/2;
            int tmpVal = arr[i];
            while(parentIdx>=0 && tmpVal > heap[parentIdx]){
                heap[childIdx] = heap[parentIdx];
                childIdx = parentIdx;
                parentIdx = (parentIdx-1)/2;
            }
            heap[childIdx] = tmpVal;
        }
        return heap;
    }

    public static void putMaxTopHeap(int[] heap, int val){
        heap[0] = val;
        int parent = 0;
        int heapLength = heap.length;
        while(parent < heapLength){
            int leftChild = parent*2+1;
            int rightChild = parent*2+2;
            int maxIdx = parent;
            if(leftChild < heapLength && heap[leftChild] > heap[maxIdx]){
                maxIdx = leftChild;
            }
            if(rightChild < heapLength && heap[rightChild] > heap[maxIdx]){
                maxIdx= rightChild;
            }

            if(maxIdx == parent){
                return;
            }

            int tmpVal = heap[maxIdx];
            heap[maxIdx] = heap[parent];
            heap[parent] = tmpVal;
            parent = maxIdx;
        }
    }
}
